The present invention is directed to digital memory systems and more particularly to an improved first-in-first-out memory system.
In digital systems a frequent design problem is providing temporary storage for several discrete units of digital data. More particularly, the design requirement is often that the sequential order in which data entered the temporary storage be maintained. Thus, the requirement is that when several discrete units of data have been written into the memory, the result upon reading the memory will be that the first unit of data written into the memory will be the first unit of data read out of the memory. A memory system which operates in accordance with this operating requirement is commonly referred to as a first in-first out (FIFO) memory system. A number of different methods for implementing FIFO memory systems are shown in the prior art including embodiments which use shift registers, random access memories and barrel registers in which memory elements are interconnected in a recirculating mode. These embodiments require extensive control logic and are most effective in large systems where the overhead costs of the peripheral control logic can be shared by a large number of FIFO memory bits. Often however, the design requirement is for a small to medium size FIFO memory block incorporated in conjunction with a digital system. It may be desired, for example, to provide a small FIFO memory on a monolithic integrated circuit designed to provide a digital data processing or data communications function. The optimum solution to a design requirement of this type would be a FIFO memory which could be implemented using conventional storage elements such as flip-flops which would then be compatible with the other digital logic circuits used to implement the logic design on the integrated circuit.
In considering the design problem of implementing a FIFO memory with flip-flops, it would be highly desirable to be able to implement the design using single rank flip-flops. A single rank flip-flop, sometimes referred to as a latch, makes use of a single pair of cross coupled coincident gates together with whatever additional logic elements are required for clocking or steering data into its input. Although the simple latch provides the static storage of digital information with the minimum number of components, it suffers from the operational disadvantage that changes in input conditions when data is written into the latch are immediately applied as the output condition of the latch. This operating feature is a particular disadvantage in FIFO memory systems because the storage elements of the FIFO memory must be connected in tandem so that stored data can be shifted from one group of storage locations to the next in orderly sequence. Thus, if single rank storage elements are connected in a FIFO memory configuration with a common clock, an attempt at entering data at the input of the FIFO memory would cause data to ripple through all of the groups memory elements in an uncontrolled manner and a malfunction would result. Thus, in prior art solutions the FIFO designer was forced to make use of double rank flip-flop configurations to implement the FIFO memory. A double rank flip-flop is one in which two cross coupled coincident gate pairs are connected in tandem such that logic signals can be applied to the input of the flip-flop in writing without affecting the logic state present at the flip-flop output. This tandem connection buffers the output of the flip-flop against changes at the flip-flop input so that the results of writing new information into the flip-flop will result in a change at the flip-flop output in a controlled fashion. This additional control allows the design of a FIFO memory system in which data can be transferred sequentially from one group of storage elements to the next in an orderly fashion. The penalty, however, for implementing a FIFO memory system using double rank storage elements is that the total component count required to implement a FIFO memory of a given size roughly double that which would be required if it were possible to implement a FIFO memory system with single rank storage elements which used only a single cross coupled coincident gate flip-flop as the basic storage element. The missing element required to implement this simpler FIFO memory structure is a logic arrangement which can provide the necessary control for sequencing data through an array of single rank storage elements.